package org.example.divideAndConquer;

import java.util.ArrayList;
import java.util.List;

/**
 * 力扣-- 分治算法
 * @Author chaigq
 * @Date 2020/11/29 下午10:47
 * @Version 1.0
 */
public class LeetCodeDivideConquer {

    /**
     * 翻转对
     * 给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
     *
     *  你需要返回给定数组中的重要翻转对的数量。
     *
     *  示例 1:
     * 输入: [1,3,2,3,1]
     * 输出: 2
     *
     *  示例 2:
     * 输入: [2,4,3,5,1]
     * 输出: 3
     *
     *  注意:
     *  给定数组的长度不会超过50000。
     *  输入数组中的所有数字都在32位整数的表示范围内。
     *
     *  Related Topics 排序 树状数组 线段树 二分查找 分治算法
     */
    public int reversePairs(int[] nums) {
        List<Long> list = new ArrayList<>();
        int res = 0;
        for (int i = nums.length -1; i >= 0; i--) {
            res += dichotomy(list, (long)nums[i]);
            list.add(dichotomy(list, (long)2 * nums[i]), (long)2 * nums[i]);
        }
        return res;
    }

    private int dichotomy(List<Long> list, Long num) {
        int start = 0;
        int end = list.size() - 1;
        while (start <= end){
            int mid = start + (end - start) / 2;
            if (list.get(mid) >= num){
                end = mid - 1;
            }else {
                start = mid + 1;
            }
        }
        return start;
    }

    /**
     * 排序矩阵查找
     *
     * 给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。
     *  示例:
     *  现有矩阵 matrix 如下：
     *  [
     *   [1,   4,  7, 11, 15],
     *   [2,   5,  8, 12, 19],
     *   [3,   6,  9, 16, 22],
     *   [10, 13, 14, 17, 24],
     *   [18, 21, 23, 26, 30]
     * ]
     *
     *  给定 target = 5，返回 true。
     *
     *  给定 target = 20，返回 false。
     *  Related Topics 双指针 二分查找 分治算法
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int row = 0;
        int col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0){
            if (matrix[row][col] > target){
                col --;
            }else if (matrix[row][col] < target){
                row ++;
            }else {
                return  true;
            }
        }
        return false;
    }











}
